#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    bool checkPartitioning(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));

        for (int i = 0; i < n; ++i)
        {
            for (int j = i; j >= 0; --j)
            {
                if (s[i] == s[j])
                {
                    dp[i][j] = j + 1 < i ? dp[i - 1][j + 1] : true;
                }
            }
        }
        /*for(auto& e : dp)
        {
            for(int i = 0; i < n; ++i) cout << e[i] << " ";
            cout << endl;
        }*/

        for (int j = 0; j < n - 2; ++j)
        {
            if (dp[j][0])
            {
                for (int i = j + 1; i < n - 1; ++i)
                {
                    if (dp[i][j + 1] && dp[n - 1][i + 1])
                    {
                        return true;
                    }
                }
            }
        }

        return false;
    }
};